package com.yusong.algorithm.dp;


import java.util.HashMap;
import java.util.Map;

/**
 * 最长上升子序列
 */
public class LIS {


    /**
     * 回溯+ 记忆化搜索
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Map<Integer, Map<Integer, Integer>> data = new HashMap<>();
        for(int i = 0; i< nums.length; i++){
            data.put(new Integer(i), new HashMap<>());
        }

        return put(0, Integer.MIN_VALUE, nums.length, nums, data);

    }

    private int put(Integer startIndex, Integer minValue, int length, int[] nums, Map<Integer, Map<Integer, Integer>> data) {
        if (startIndex > (length - 1)) {
            return 0;
        }
        if(null != data.get(startIndex).get(minValue)){
            return data.get(startIndex).get(minValue);
        }


        int currentValue = nums[startIndex];
        int maxLength = 0;
        if (minValue >= currentValue) {
            maxLength =  put(startIndex + 1, minValue, length, nums, data);
        }else {
            maxLength = Math.max(put(startIndex + 1, minValue, length, nums, data),
                    put(startIndex + 1, currentValue, length, nums, data) + 1
            );

        }


        data.get(startIndex).put(minValue, maxLength);

        return maxLength;
    }
}
